package java学习.代码随想录.动态规划.背包;

import java.util.Arrays;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/8/19 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 完全背包 {
    /**
     * 物品为：
     *
     *       重量   价值
     * 物品0	  1	   15
     * 物品1	  3	   20
     * 物品2	  4	   30
     * 每件商品都有无限个！
     *
     * 问背包能背的物品最大价值是多少？
     */
    /**
     * 1. dp[j] 背包容量为j 可装下的最大价值
     * 2. dp[j] = max(dp[j],dp[j-w[i]]+v[i])
     * 3. 初始化
     * 重复背包
     */
    public static int bagproblem(int[]w , int[]v , int bagsize ){
        int[] dp = new int[bagsize+1];
        for (int i = 0; i < w.length; i++) {
            for (int j = w[i]; j <=bagsize ; j++) {
                dp[j] = Math.max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[bagsize];
    }
//    遍历顺序翻转
    public static int bagproblemReverse(int[]w , int[]v , int bagsize ){
        int[] dp = new int[bagsize+1];
            for (int j = 0; j <=bagsize ; j++) {
                for (int i = 0; i < w.length; i++) {
                    if (j>=w[i]){
                        dp[j] = Math.max(dp[j],dp[j-w[i]]+v[i]);
                    }
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[bagsize];
    }
    //    二维数组
    public static int bagproblemTwo(int[]w , int[]v , int bagsize ){
        int[][] dp = new int[w.length+1][bagsize+1];
            for (int i = 1; i <= w.length; i++) {
                for (int j = 1; j <=bagsize ; j++) {
                    if (j>=w[i-1]){
                    dp[i][j] = Math.max(dp[i-1][j],
            /**
             * dp[i][j-w[i-1]]+v[i-1]  而不是 dp[i-1][j-w[i-1]]+v[i-1]
             * dp[i-1] 是指 存放前i-1 物品(只选一次) 最大价值 的基础上 存放了 第i件物品，
             *      此时 第i件已经放入了，因为01背包是不能重复存放的；
             * dp[i-1] 是指 存放前i-1 物品(只选一次) 最大价值 的基础上，再加上第i件物品 todo 都只能选择物品一次。
             * dp[i]  是指 第i件物品是可以重复存放的，是存放当前物品时，重量为j-w[i-1]的最大价值
             * 因为 可重复拿物品，因此放东西之后，不依赖于之前的，画一遍
             */
                            dp[i][j-w[i-1]]+v[i-1]);
                }else {
                    dp[i][j] = dp[i-1][j]; // 表示不加入第i-1个物品
                }
            }
        }
        for (int i = 0; i <=w.length; i++) {
            for (int j = 0; j <=bagsize; j++) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println(" ");
        }
//        System.out.println(Arrays.toString(dp));
        return dp[w.length-1][bagsize];
    }

    // 三重循环 物品可重复选择。
    public static  int bagproblemFork(int[]w , int[]v , int bagsize ){

        int [][]dp = new int[w.length+1][bagsize+1];
        for (int i = 1; i <=w.length; i++) {
            for (int j = 1; j <=bagsize; j++) {
                for (int k = 0; k*w[i-1]<=j ; k++) { // 每件物品能放入背包的最多 个数 k。
                    dp[i][j]  =  Math.max(dp[i-1][j],dp[i-1][j-w[i-1]*k]+k*v[i-1]);
                    //                    不装             装
                }
            }
        }
        for (int i = 0; i <=w.length; i++) {
            for (int j = 0; j <=bagsize; j++) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println(" ");
        }
        return dp[w.length][bagsize];
    }

    public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagWeight = 4;
        System.out.println(bagproblem(weight,value,bagWeight));
        System.out.println("---------");
        System.out.println(bagproblemReverse(weight,value,bagWeight));

        System.out.println("---------");
        System.out.println(bagproblemTwo(weight,value,bagWeight));

        System.out.println("---------");
        System.out.println(bagproblemFork(weight,value,bagWeight));


        int[][] a =  {{2}, {1, 1}, {2, 2}, {1}, {3, 3}, {2}, {4, 4}, {1}, {3}, {4}};

    }
}
